package subjectlist;


/**
 * 寻找一条从左上角（arr[0][0]）到右下角（arr[m-1][n-1]）的路线，使得沿途经过的数组中的整数的和最小
 */
public class U如何在二维数组中寻找最短路线 {


    /**
     * 动态规划其实也是一种空间换时间的算法，通过缓存计算的中间值，从而减少重复计算的次数，提高算法的效率。
     * 方法一从arr[m-1][n-1]开始逆向通过递归来求解，采而动态规划要求正向求解，以便利用前面计算出来的结果。
     * 对于本题而言，显然f（i,0）=arr[0][0]+…+arr[i][0]，f[0,j]=arr[0][0]+…+arr[0][j]。
     * 根据递推公式f（i,j）=min{f（i-1,j）, f（i,j-1）}+arr[i][j]，从i=1，j=1开始顺序遍历二维数组，
     * 可以在遍历的过程中求出所有的f（i,j）的值，同时，把求出的值保存到另外一个二维数组中以供后续使用。
     * 当然，在遍历的过程中可以确定这个最小值对应的路线，在这种方法中，除了求出最小值外顺便还打印出了最小值的路线，实现代码如下
     */

    public static int getMinPath(int[][] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int row=arr.length;
        int col=arr[0].length;

        //用来保存计算的中间值
        int[][]cache=new int[row][col];
        cache[0][0]=arr[0][0];

        for (int i=1; i <col ; i++) {
            cache[0][i]=cache[0][i-1]+arr[0][i];
        }
        for (int j=1; j <row ; j++) {
            cache[j][0]=cache[j-1][0]+arr[j][0];
        }
        //在遍历二维数组的过程中不断把计算结果保存到cache
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //可以确定选择的路线为arr[i][j-1]
                if(cache[i-1][j]>cache[i][j-1]){
                    cache[i][j]=cache[i][j-1]+arr[i][j];
                    System.out.print("["+i+","+(j-1)+"]");
                }else {
                    cache[i][j]=cache[i-1][j]+arr[i][j];
                    System.out.print("["+(i-1)+","+j+"]");
                }
            }
        }
        System.out.println("["+(row-1)+","+(col-1)+"]");
        return cache[row-1][col-1];
    }

    public static void main(String[] args) {
        int[][]arr={
                {1,4,3},
                {8,7,5},
                {2,1,5}
        };
        System.out.println(getMinPath(arr));
    }


}
